import numpy as np

def two_opt_swap(route, i, j):
    new_route = route.copy()
    # 将i到j之间的路径反转
    new_route[i:j+1] = new_route[i:j+1][::-1]
    return new_route

def two_opt(individual, cities, max_no_improvement=5):
    """2-opt局部搜索算法"""
    from problems.TSP.fitness import total_distance   
    best_route = individual.copy()
    best_distance = total_distance(best_route, cities)
    improved = True
    iterations = 0
    
    while improved and iterations < max_no_improvement:
        improved = False
        for i in range(1, len(best_route) - 2):
            for j in range(i + 1, len(best_route)):
                # 跳过相邻边
                if j - i == 1:
                    continue
                
                # 尝试交换
                new_route = two_opt_swap(best_route, i, j)
                new_distance = total_distance(new_route, cities)
                
                # 如果找到更好的解
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improved = True
                    break  # 跳出内层循环
            
            if improved:
                break  # 跳出外层循环
        
        iterations += 1
    
    return best_route, best_distance